This invention relates generally to the field of telecommunications and in particular to a more efficient method for selecting a transmission path in a connection-oriented network.
It is apparent that connection-oriented networks will play an increasing role in data networking. Connection-oriented networking offers important advantages over connectionless networks, including the advantage of providing Quality of Service (QoS) guarantees, which facilitate new classes of applications such as multimedia, voice over internet protocol, and other real-time services.
A connection-oriented network includes of a set of switches interconnected by point-to-point links or interfaces. The switches support two kinds of interfaces: user-network interfaces (UNI) and network-to-network or network-node interfaces (NNI). A UNI connects end-systems (hosts, routers, and so on) to a switch, while an NNI may be imprecisely defined as an interface connecting two switches together. More precisely, however, an NNI is any physical or logical link across which two switches exchange the NNI protocol. Various NNI protocols, such as the Private Network-Network Interface (PNNI) protocols designed for asynchronous-transfer-mode networks, include a routing protocol that exchanges metrics, such as available and maximum bandwidth, cell loss ratio (CLR), cell delay variation (CDV), and cell transfer delay (CTD), related to Quality of Service (QoS). Routes are then computed using the data collected by the routing protocol. Most commonly-used route determination algorithms (such as Dijkstra shortest path algorithm) use a single, cumulative metric such as link weightings (i.e., administrative weight, hereinafter AW) or costs that relate to the efficient use of the network.
For example, cell loss ratio (CLR) is one of the metrics, or measurements, that can used to determine whether a given network cell, consisting of a link or node or concatenation of links and nodes, can meet the requested quality of service (QoS). Cell delay variation (CDV) and cell transfer delay (CTD) are other such metrics or measurements. In contrast, administrative weight (AW) is a measurement of cost that relates to the efficient use of the network.
Other path selection algorithms, as the one proposed in the PNNI v1.0 standard, use a simple Generic Connection Admission Control (SGCAC) procedure to account for bandwidth. However, neither the SGCAC nor the complex GCAC proposed in PNNI v1.0 is effective in providing the QoS guarantees expected by many data networking customers.
In more detail, the problems in connection-oriented data networking arise out of the following typical existing situations.
As an example of routing and signaling in a connection-oriented network, the PNNI signaling protocol is used to set up asynchronous-transfer-mode switch connections between the source end-system and the destination end-system. The UNI signaling request is mapped into PNNI signaling at the ingress switch. The PNNI signaling is remapped back into UNI signaling at the egress switch. The PNNI signaling protocol is an extension of the UNI signaling and incorporates additional Information Elements (IEs) for PNNI related parameters such as the Designated Transit List (DTL). The PNNI routing protocol is used to disseminate topology, loading conditions and reachability data. For scalability reasons, the notion of hierarchical peer groups is created with Peer Group Leaders (PGLs) elected for each peer group. The PNNI routing protocol is used for hierarchical aggregation and propagation of information. Data about a peer group is aggregated by the peer group leader, which then distributes this data to all the nodes in the higher-level peer group in PNNI Topology State Packets (PTSPs). Thus, aggregated data is passed xe2x80x9cupxe2x80x9d the hierarchy by peer group leaders. Nodes in a peer group receiving data sent by one of their peer nodes at the higher levels of hierarchy distribute the received data xe2x80x9cdownxe2x80x9d the hierarchy. This allows a switch to maintain a view of the xe2x80x9cglobalxe2x80x9d topology with reachability information for endpoints.
The PNNI routing protocol supports a large number of link and node state parameters that are advertised by the switches to indicate their current state at regular intervals which enables QoS-sensitive routing. This includes two types of parameters: attributes, such as Available Cell Rate, Cell Rate Margin, Variance Factor, used to determine whether a given network link or node can meet requested QoS; and metrics, such as maxCDV, CTD, CLR, AW, that are used to determine whether a given path, consisting of a set of concatenated links and nodes (with summed link metrics), can meet the requested QoS. The link metrics and attributes are per port per service category. Individual nodes (physical or logical) will need to determine and then advertise the values of these parameters for themselves.
As a result of these exchanges, a topology database is created, which has reachability information for all the network nodes and the available resources on the network links and nodes. All network nodes can obtain an estimate of the current state of the entire network. Unlike most current link state protocols, the PNNI routing protocol advertises not only link metrics but also nodal information.
When a switch receives a connection setup request, a number of steps are executed. Among these are Connection Admission Control (CAC), Generic Connection Admission Control (GCAC) and shortest path computation. CAC is used to determine if the requested connection can be admitted without violating QoS guarantees of established connections. CAC is a local switch function, and is, dependent on the architecture of the switch and local decisions on the strictness of QoS guarantees required by the switch. The other two algorithms, GCAC and shortest-path computation, are used by the ingress node receiving a connection setup request to determine a shortest-path hierarchical route for the connection while ensuring that all the links on the path have the available cell rate (bandwidth) requested for the connection. This form of routing, where the ingress node determines the shortest-path for the connection, is referred to as source routing. The PNNI v1.0 standard specifies two GCAC algorithms: simple GCAC and complex GCAC. Either of these algorithms can be used to determine if each link on a selected path has the requisite available cell rate (bandwidth) for the connection. The shortest path computation is essentially an execution of a shortest-path algorithm, such as Dijkstra""s or Bellman-Ford""s, with the link and node weights set to those of the metrics advertised in the received topology information.
Since PNNI networks are hierarchical, the shortest-path computed by the ingress node (after applying Dijkstra""s algorithm and the GCAC available cell rate check algorithm) does not specify the exact set of switches through which the connection must be routed. Instead, it specifies a stack of Designated Transit Lists (DTLs), one identifying the physical switches in its peer group, and others identifying logical switches in higher-level peer groups. The DTLs are passed as parameters in the SETUP message. This eliminates the need for intermediate nodes (except border nodes of peer groups) to perform route selection. The border node of each peer group is involved in route selection since nodes outside a peer group P do not have a detailed picture of the topology and loading conditions of the peer group P. The border node through which the connection setup enters the peer group computes a DTL for its peer group and places this on the stack of DTLs as it propagates the PNNI SETUP message.
Once a path has been selected for the connection, each node on the path executes CAC (Connection Admission Control) to ascertain that it can admit the connection without violating guarantees for existing connections. Each node in the path needs to perform its own connection admission control because its own state may have changed since it last advertised its state with the network used for the GCAC at the ingress or border node.
If the connection admission control procedure is successful, each node then programs the switch fabric with channel identifier translation information and with information for user-plane algorithms, such as scheduling, UPC (Usage Parameter Control), traffic shaping, etc.
The signaling protocol is used to send a message from node to node to complete connection setup. Once a connection is set up, user data packets are forwarded through each node according to the channel identifier translation information. Since the route selection phase (executing shortest-path and GCAC algorithms) could consume a significant amount of time, route precomputation is suggested in Appendix H of the PNNI v1.0 specification. Precomputing routes could potentially speed up the route selection process. With precomputed paths, a connection setup request is handled by the ingress switch first determining the destination switch (logical node) through which to reach the called endpoint. If a precomputed route exists to the destination switch, the GCAC algorithm is applied to each link of the precomputed path to check for cell rate availability.
If this test passes, the route selection step is complete. If not, an xe2x80x9con-the-flyxe2x80x9d route selection, consisting of both shortest-path and GCAC algorithm executions, is needed. Again, each node in the path needs to perform its own connection admission control because its own state may have changed since it last advertised its state within the network used for the GCAC at the ingress or border node.
The new services and reduced rates made possible by such peer groups of networks and nodes have been very attractive to users, but poorly-controlled delays and occasional failure of connectability have been drawbacks.
In the copending patent application of two of us with others, Ser. No. 09/188,023, filed Nov. 6, 1998, a dynamic programming method is disclosed for determining the length of a shortest path from a source node to any of v other nodes in the network with delay equal to an amount less than a specified time. A table is then built for such shortest-path routes for different specified delay times, so that a user may specify a maximum delay time as one of the requirements for quality of service. Because of the demands for computer time made by this method for large and complex networks, it is desirable to improve the method to be more efficient in use of computer time, particularly when the table must be supplemented by xe2x80x9con-the-flyxe2x80x9d calculations.
According to the present invention, a more efficient delay-based path selection is provided in connection-oriented data networking. The connection-requesting user not only specifies a delay threshold T for the incoming request but also specifies a delay threshold tolerance xcex5 within which the path delay should be satisfied. The method of the invention accesses stored values of the topology of the network and delay-related parameters for a set of links between different ones of the plurality of packet switches and provides to the user a delay-based shortest-path connection to one or more other users via at least one of said packet switches. The connection is provided by testing combinations of links by scaling the permissible delay threshold to a value xcfx84, appropriately chosen to ensure the user-specified delay threshold is satisfied to within the user-specified tolerance, correspondingly scaling the, delay measure on each link, and then truncating all the scaled values to integers, and accumulating the scaled link delays for the connection using a dynamic programming algorithm. The method exploits the new user specifications and computes paths from one source to all destinations in a coamputationally efficient manner.
In a first non-iterative implementation of the present invention, xcfx84 is set to min (T, (nxe2x88x921)/xcex5), where T and xcex5 are respectively the delay threshold and the threshold tolerance specified by the user, and n is the number of nodes in the network. The dynamic programming algorithm computes Table L(v, xcfx84) and Table P(v, xcfx84), where L is the length of the path from a given node to node v and P encodes the shortest path from the given node to node v whose delay is no more than xcfx84. The method then computes the delays for each link in the original data for the topology of the network for each of the paths P(v, xcfx84) and store the delays in a table D(v). The algorithm provides outputs L(v, xcfx84) and D(v) and terminates.
The time complexity of this algorithm is min(ET, E(nxe2x88x921)/"xgr"), and thus can be considerably faster than the dynamic programming algorithm used without scaling.
In a second implementation of the invention, which is the iterative scaling algorithm, the time complexity is further reduced to 4ED/"xgr", where D is the maximum hop length of the optimal path, and E is the number of links in the network. The method of this implementation first sets xcfx84=xcfx840 (a small number  less than  less than T) and scales all of the link delays. The dynamic programming algorithm is then used to compute Table L(v,xcfx84) and Table P(v, xcfx84).
The method then computes the delays for each path P(v, xcfx84) using unscaled original link delays and stores the delays in a table D(v). If the condition exists that D(v) greater than T(1+xcex5) and 2xcfx84 less than n/xcex5, set xcfx84=2xcfx84, rescale all delay parameter values, truncate them to integers, and recompute Table L(v,xcfx84) and Table P(v,xcfx84), else copy L(v,xcfx84) to L(v) and P(v,xcfx84) to P(v) and terminate.
The table calculated during the last iteration of DSA (Dynamic Scaling Algorithm) contains the constrained shortest paths.
The method according to either implementation of the present invention has two compelling advantages. It generates paths from one source to multiple destinations, an attribute that is critical in designing route caching algorithms that improve the grade of service. Further, it greatly improves computational speed.
Further features and advantages of the present invention, as well as the structure and operation of various embodiments of the present invention are described in detail below with reference to the accompanying drawing.